This invention relates generally to inter-class schedulers for digital link systems, including asynchronous transfer mode (ATM) telecommunications systems, and, more particularly, provides novel inter-class schedulers employing statistical priority guaranteed queuing (SPGQ) and generic cell-rate algorithm priority guaranteed queuing (GCRA-PGQ).
The systems and methods disclosed herein are discussed with particular application to ATM systems. However, those skilled in the art will appreciate that the inventive subject matter disclosed herein is equally applicable to other settings in which a plurality of devices transmit and/or receive digital signals over a bandwidth-limited link, such as systems where multiple client or end-user machines communicate with a host.
Information regarding ATM systems can be found in the ATM Forum, xe2x80x9cATM User-Network Interface Specification,xe2x80x9d Version 3.1, September, 1994, and in Martin de Prycker, xe2x80x9cAsynchronous Transfer Mode: Solution for Broadband ISDN, xe2x80x9d Ellis Horwood, N.Y. 1993, both of which are incorporated by reference herein. Aspects of ATM systems are also discussed in U.S. Pat. Nos. 5,818,815; 5,794,025; and 5,768,259, also incorporated by reference herein.
An advantage of high bandwidth, fixed length cell based transfer mode techniques such as ATM, is the capability of high-speed, low-delay multiplexing and switching of different types of user information trafficxe2x80x94including data, voice, image and videoxe2x80x94over the same network, while optimizing bandwidth and resources utilization.
In ATM connection-oriented networks, the end-to-end traffic of data for one user, between the source and the destination, is represented by a Virtual Connection (VC); several Virtual Connections can be grouped in a Virtual Path (VP) that can be switched as a unit.
An ATM system segments user traffic into fixed-length 53-byte cells. A 5-byte header in each cell typically includes a virtual channel identifier (VCI) and a virtual path identifier (VPI) associated with the corresponding cell. The VCI and VPI fields together identify the virtual connection that is established when a user requests a network connection in an ATM system. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling, and the devices that accomplish this task are schedulers.
As employed in ATM and other digital link systems, an inter-class scheduler is a device that monitors the status of an input queue for each class of service (voice, video, and other digital signals), updates the eligibility data of service of the class, and according to some predefined criteria, makes decisions about the class to be serviced at the next transmit opportunity. The digital switching apparatus utilizes this decision outcome to select a particular class for the next transmit opportunity.
In essence, the inter-class scheduler enables the digital link system to determine which class will next receive a share of limited bandwidth and processor resources. These decisions are vital to the performance of bandwidth-limited digital link systems.
A major problem to be resolved in cell-based networks is congestion control. Since the cells are short, no space is allocated in the header to enable error recovery for the cell payload. If one cell of the block has been lost or discarded by the network in case of network congestion, error recovery is performed at the higher-level by recovery protocols retransmitting the user data block. Since the error rate is normally quite low in the internode links, the loss of cells due to random error is not generally a problem. However, when a node discards cells based upon detection of traffic congestion, it is unlikely that these cells will come from a small number of logical data blocks. Consider, for example, a worst case scenario, in which 1000 messages come from 1000 different connections. Under such a circumstance, the discarding of 1000 cells, where the average user data block length is 2K Bytes (a low estimate) sent as 43 cells, can cause the network to absorb a retransmission of 43,000 cells.
Depending on the type of traffic conveyed over the network, congestion can damage the quality of traffic beyond acceptable limits. For voice applications it is more acceptable to lose data than to excessively delay it. For file applications it is more acceptable to delay the data than to lose any portion of it. That is why the ATM networks provide different Quality of Service (QoS) guarantees for different classes of service. In order to meet the QoS, the network nodes have to control the traffic congestion both at connection admission time and once the connection is established.
A first control on traffic congestion, once the connection is established, is performed by a policing function implemented in a device, referred to as the xe2x80x9cpolicer,xe2x80x9d of the network access node adapter. The policer will detect and penalize violations of the peak cell rate of xe2x80x9ccurrentxe2x80x9d traffic compared to the peak cell rate required at call set-up.
A second control of traffic congestion consists in shaping the output network node traffic by spacing cell departures such that the time between two departures of cells for a same connection is never below the minimal value negotiated at connection setup time. The multiplexing of spaced cells tends to decrease the xe2x80x9cburstinessxe2x80x9d of the aggregate traffic, permitting a better utilization of the network resources.
The policing function is typically implemented in the network nodes by a xe2x80x9cpolicerxe2x80x9dthat forms part of the high speed adapter cards in the devices accessing the network. The shaping function is implemented in the network nodes by a xe2x80x9cshaperxe2x80x9d that controls the sending of the output traffic cells and is also part of the high ed adapter cards.
The policing function proposed as a standard by the ITU (International Telecommunications Union), is the Generic Cell Rate Algorithm (GCRA). Details of the GCRA are given in the ATM Forum, xe2x80x9cATM User-Network Interface Specificationxe2x80x9d, Version 3.0, 1994, incorporated by reference herein. Those skilled in the art will appreciate that commercially-available, application-specific integrated circuits (ASICs) have been developed to implement GCRA.
The role of the GCRA is, for each connection, to monitor the traffic arriving upstream according to the cell period T (T corresponds to the inverse of the peak cell rate R) and a given tolerance tau on this period. Basically, a cell is assumed to be conforming if the time elapsed between the arrival of two consecutive cells (belonging to the same connection) is greater than or equal to Txe2x80x94tau . If not, the cell is assumed to be nonconforming and is tagged and possibly discarded.
The policer discards cells not only because the source of traffic has violated the parameters negotiated at connection establishment, but also because of a distortion in the cell stream commonly referred to as xe2x80x9cjitterxe2x80x9d or Cell Delay Variation (CDV). This distortion is due to the queuing of the cells at each intermediate network node and more generally the multiplexing of the cells on the output lines. The magnitude of the xe2x80x9cjitterxe2x80x9d depends on many parameters, including the connection peak rate; the peak rate of the other connections that share the same link; the link load; and the number of nodes passed through.
The foregoing discussion demonstrates that considerable design and implementation effort has been expended in attempting to control congestion problems in digital link systems. In this regard, it is also clear that inter-class schedulers must be sufficiently efficient to limit adverse effects of congestion. Thus, an effective inter-class scheduler should have several properties. First, it should provide a minimum bandwidth guarantee for each class. Second, it should provide exclusive allocation of unused bandwidth to the highest priority class that requires it. In addition, it should enable provisioning of work-conserving service.
Inter-class schedulers can be categorized into absolute or xe2x80x9cstaticxe2x80x9d priority schedulers on the one hand, and dynamic priority schedulers on the other. The category of dynamic priority schedulers can be divided into those which provide a fixed minimum bandwidth guarantee, and those which provide a programmable minimum bandwidth guarantee.
One deficiency of absolute priority schedulers is that they cannot guarantee either bandwidth or cell delay for any traffic classes other than the one with the highest priority. In particular, minimum bandwidth to the lower classes can not be guaranteed because it will not be serviced until all packets or cells belonging to classes with higher priorities are services. If the system assigns a high priority to an application which seeks to use the entire bandwidth, lower-priority classes may be completely locked out and be denied any service opportunity.
In an attempt to eliminate this problem, schedulers using a Priority Guaranteed Queuing (PGQ) paradigm have been implemented. The PGQ paradigm is a absolute priority scheduler combined with a guaranteed servicing concept. PGQ schedules cells belonging to different priority classes within a virtual link. PGQ attempts to achieve bandwidth guarantees for all classes by offering each of the classes at least a guaranteed portion of the total bandwidth available to the set of classes to which the PGQ algorithm been applied.
An ideal PGQ scheduler (such as GCRA-PGQ) is highly accurate because it maintains a history of previous transmissions and supports variable size packets. Implementation of this algorithm, however, is relatively complex and costly in terms system resources, and since scheduler accuracy may not be an overriding system objective, the additional cost in resources may not be worth the modest accuracy advantage.
With the rapid expansion of Internet and other digital link systems, more and more digital classes of service are being defined and demanded by customer/clientsxe2x80x94including voice, video, and internet-related digital data. As this occurs, more and more resources will be required to provide inter-class scheduling to meet the quality of service (QoS) requirement of each class. For example, a typical digital packet-switching system may handle as many as 8 classes, rendering a full PGQ scheduler relatively complex and costly. Implementation of an inexpensive, efficient mechanism for priority guaranteed queue scheduling would provide a competitive advantage.
Accordingly, there exists a need for improved inter-class scheduling systems and methods for digital link systems.
It is accordingly an object of the invention to provide low-cost, simple and efficient mechanism to provide priority guaranteed queuing.
It is another object of the invention to provide such methods and apparatus that avoid the burden of implementing a full priority guaranteed queuing scheduler typical of the prior art.
It is a further object of the invention to provide such methods and apparatus that minimize cell delay variation for high priority classes.
Other general and specific objects of the invention will in part be obvious and will in part appear hereinafter.
The foregoing objects are attained by the invention, one aspect of which provides an inter-class scheduler utilizing Statistical Priority Guarantee Queuing (SPGQ), a method of modifying the pure-priority behavior of an absolute priority scheduler, by xe2x80x9celevatingxe2x80x9d the priority of otherwise low-priority classes in accordance with a statistical process. In accordance with this aspect of the invention, the scheduler determines whether a number within a range produced by a uniform random number generator lies within a sub-range proportional to the programmed statistical guarantee for a given class. If the number lies within the sub-range associated with a given class, then the priority of that class is elevated to a higher priority when both are eligible to transmit.
Another aspect of the invention provides an inter-class scheduler utilizing Generic Cell-Rate Algorithm Priority Guarantee Queuing (GCRA-PGQ). In accordance with this aspect of the invention, GCRA-PGQ operates as a strict priority mechanism until a class exceeds a GCRA xe2x80x9ctraffic shapexe2x80x9d or threshold representative of guaranteed bandwidth, whereupon the system will lower the priority of service accorded that class.
The invention will next be described in connection with certain illustrated embodiments; however, it should be clear to those skilled in the art that various modifications, additions and subtractions can be made without departing from the spirit or scope of the claims.